package com.zwj.interview.回溯;

import java.util.LinkedList;
import java.util.List;

/**
 * 题目：给定一个没有重复数字的正整数集合，请找出所有元素之和等于某个给定值的所有组合。
 * 同一个数字可以在组合中出现任意次。例如，输入整数集合[2，3，5]，元素之和等于8的组合有3个，
 * 分别是[2，2，2，2]、[2，3，3]和[3，5]
 *
 * 无重复数字数组的目标和组合
 */
public class 无重复数字数组的目标和组合 {

    public List<List<Integer>> combination(int[] nums, int target) {
        List<List<Integer>> result = new LinkedList<>();
        // 记录回溯算法的递归路径
        LinkedList<Integer> combination = new LinkedList<>();
        helper(nums, target, 0, combination, result);
        return result;
    }


    /**
     * target是组合combination中元素之和的目标值。每当在组合中添加一个数字时，就从target中减去这个数字。
     * 当target等于0时，组合中的所有元素之和正好等于target，因此也就找到了一个符合条件的组合
     *
     * @param nums
     * @param target
     * @param i
     * @param combination
     * @param result
     */
    private void helper(int[] nums, int target, int i, LinkedList<Integer> combination, List<List<Integer>> result) {
        //这个target不断的变化，当target减去这个组合中的所有数字为0的时候，说明这个组合就满足
        if (target == 0) {
            result.add(new LinkedList<>(combination));
        } else if (target > 0 && i < nums.length) {
            //不选择nums[i]的情况
            helper(nums, target, i + 1, combination, result);
            combination.add(nums[i]);
            //选择nums[i]的情况，target减去nums[i],这里的下标在选择了nums[i]之后，还从i开始，是因为题目中允许数字重复使用
            helper(nums, target - nums[i], i, combination, result);
            //撤回选择
            combination.removeLast();
        }
    }



}
